import java.util.LinkedList;

public class Test {


    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);
        myLinkedList.addLast(12);
        myLinkedList.addLast(12);
        myLinkedList.addLast(12);

        myLinkedList.display();

        //myLinkedList.addIndex(2,188);
        myLinkedList.clear();
        System.out.println("================");
        myLinkedList.display();

        LinkedList<Integer> list = new LinkedList<>();
        list.clear();
    }



    public static void main7(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.show();
        System.out.println("====================");

        mySingleList.createLoop();

        //mySingleList.show();

        System.out.println(mySingleList.hasCycle());

    }

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {

        MySingleList.ListNode newH = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newH;
        //这2个引用都不为空 表示 2个链表当中是存在数据的
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tmp.next = list1;
                list1 = list1.next;
                //tmp = tmp.next;
            }else {
                tmp.next = list2;
                list2 = list2.next;
                //tmp = tmp.next;
            }
            tmp = tmp.next;
        }
        if(list1 != null) {
            tmp.next = list1;
        }
        if(list2 != null) {
            tmp.next = list2;
        }
        return newH.next;
    }

    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {

        int lenA = 0;
        int lenB = 0;
        //假设pl表示的链表是长的链表
        //假设ps表示的链表是短的链表
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;

        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        pl = headA;

        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        ps = headB;

        int len = lenA - lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //走完上述代码：1. pl一定指向长度链表 ps一定指向短的链表  len是一个正数
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //pl走了差值步 现在可以一起走了
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        //没有交点 返回null
        if(pl == null) {
            return null;
        }
        return pl;
    }

    public static void createCut(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        headB.next.next = headA.next.next;
    }

    public static void main5(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.show();
        System.out.println("====================");
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(22);
        mySingleList2.addLast(33);
        mySingleList2.addLast(44);
        mySingleList2.addLast(145);
        mySingleList2.addLast(156);
        mySingleList2.show();
        System.out.println("====================");

        createCut(mySingleList.head,mySingleList2.head);
        mySingleList.show();
        mySingleList2.show();
        MySingleList.ListNode cutNode = getIntersectionNode(null,mySingleList2.head);
        if(cutNode == null) {
            System.out.println("没有交点...");
        }else {
            System.out.println(cutNode.val);
        }
    }

    public static void main4(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(34);
        mySingleList.addLast(45);
        mySingleList.addLast(56);
        mySingleList.show();
        System.out.println("====================");
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(22);
        mySingleList2.addLast(33);
        mySingleList2.addLast(44);
        mySingleList2.addLast(145);
        mySingleList2.addLast(156);
        mySingleList2.show();
        System.out.println("====================");
        MySingleList.ListNode newH = mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList.show(newH);
    }

    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(12);
        mySingleList.addLast(31);
        mySingleList.addLast(14);
        mySingleList.addLast(51);
        mySingleList.addLast(26);
        mySingleList.show();
        System.out.println("====================");

        MySingleList.ListNode newHead = mySingleList.partition(30);
        mySingleList.show(newHead);

        //System.out.println(mySingleList.kthToLast(0));

        /*MySingleList.ListNode ret = mySingleList.middleNode();
        System.out.println(ret.val);
*/
        /*MySingleList.ListNode ret = mySingleList.reverseList();
        mySingleList.show(ret);*/
        //mySingleList.show(mySingleList.reverseList());
    }

    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(34);
        mySingleList.addLast(34);

        mySingleList.show();

       /* mySingleList.removeAllKey(34);

        mySingleList.show();*/

        mySingleList.clear();

        System.out.println("==============");
        mySingleList.show();


    }
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();

        //mySingleList.createList();
        mySingleList.addFirst(12);
        mySingleList.addFirst(23);
        mySingleList.addFirst(34);
        mySingleList.addFirst(45);
        mySingleList.addFirst(56);

        mySingleList.show();//56 45 34 23 12

        mySingleList.addLast(19);
        mySingleList.addLast(29);
        mySingleList.show();//56 45 34 23 12 19 29


        mySingleList.addIndex(3,888);

        mySingleList.show();//888 56 45 34 23 12 19 29

        System.out.println(mySingleList.size());

        System.out.println(mySingleList.contains(156));

    }
}